Comments on “Process Synchronization in Database Systems”

In a recent paper [4], Schlageter introduced a formal theory of database concur-rency control. Theorems 3.1 and 3.2 of that paper imply that serializability of transaction schedules can be tested in polynomial time, contradicting NP-com-pleteness results in [2, 31. The following counterexample demonstrates that the results of [4] are in error. EXAMPLE 1 Notation r<[U] means “process i reads variable u”; wi[u] means “process i writes into variable v. ” Sequences of r ’ s and w ’ s denote schedules. Process Pi ” initializes the database state and PO,, reads the final database state. PI, Pz, and Pa are user processes. Theorem 3.1 states that a schedule is serializable only if whenever two processes have conflicting actions, ail pairs of conflicting actions appear in the same order. (Two actions conflict if they operate on the same variable and one of them is a write action.) Consider schedule S: Si does not satisfy the condition of the theorem because (1) rl[x] conflicts with and precedes w$x]; while (2) w,[x] conflicts with and precedes w,[x]. Nonetheless S1 is equivalent to the following serial schedule: SI = Wi”[X]Win[Y]Win[Z]r*[X]W~[Z]W~[X]~2[Y]W2[X]IS[Z]W3[X]r~but[X]r~ut[Y]r~~~[Z]. Thus S1 is serializable, contradicting Theorem 3.1. Cl Theorem 3.2 fails on the same example. Theorem 3.2 states that a schedule is serializable if its “reduced dependency graph ” is acyclic. But Si produces th